The present invention relates generally to proving plaintext knowledge of a message, encrypted in a ciphertext, in computer systems. Methods and systems are provided for such implementing such proofs, as well as authentication methods based on group signature schemes which utilize these proofs.
Proving plaintext knowledge of a message encrypted in a ciphertext is required for various cryptographic protocols used in computer systems. Group signature schemes are one such example. These protocols enable computers using the group scheme to authenticate their messages on behalf of a group. In a group signature scheme, a group manager supplies distinct secret keys to all user computers in the group. The user computers can then sign messages anonymously in name of the group. A verifier computer, which receives a signed message, can verify that the message was signed by a member of the group, but cannot determine which user was the actual signer. The scheme provides for an additional entity, the “opener”, which is the only entity able to recover the identity of the signer. The opener may be the group manager or other designated authority which is trusted to “open” signatures and extract user identities when necessary, e.g. in the case of system abuse. Group signatures are particularly useful in scenarios where remote devices need to be authenticated but privacy requires that individual devices can only be identified by a designated authority. Examples include: government-issued electronic identity (eID) cards, where each issued smart card creates identity claims as signed statements about its attributes, without needing to fully identify its owner, remote anonymous attestation of computing platforms, where devices prove which software they execute; or vehicle-to-vehicle (V2V) communication, where vehicles inform each other about their position, speed, observed conditions, etc., via short-range radio communication.
Group signature schemes using lattice-based cryptography have received a lot of attention. Early lattice-based group signature schemes had signature sizes that were linear in the number of group members, and were therefore mainly proofs of concept and unsuitable for practical application. Later schemes were asymptotically more efficient with signature sizes logarithmic in the number of users. However, practical instantiations of lattice-based group signature schemes remain a challenge.